The present invention relates to product sum operation processing apparatus and more particularly to a product sum operation processing apparatus generally used for multiplication of digital numbers with signs.
The product sum operation is indicated by the following formula: EQU Y=C.+-.(Ai.times.Bi) (1)
where Ai represents a multiplier, Bi represents a multiplicand, C represents an augend/minuend and Y a product sum operation result. Usually, either addition or subtraction is selected.
Conventionally, in order to perform multiplication at a high speed and with a small circuit scale so as to realize the above product sum operation, a technique which improves Booth coding, called improved Booth coding, has been used. The improved Booth coding is widely known as a high-speed multiplication method and is described in, for example, "Electronic Computer 2" by Hajime IIzuka, pp.31-33, Corona-sha, 1990. In the improved Booth algorithm, even digits j of a multiplier are picked up so that the multiplier may be divided by 3 bits which correspond to each digit j, the preceding digit j+1 and the succeeding digit j-1 to determine partial multipliers (PAi)j each being of 3 bits, the whole of a multiplicand is shifted in accordance with values of the individual partial multipliers to determine partial products (hereinafter referred to as sub-partial products) of the partial multipliers and the results of shift operation of the whole of the multiplicand, and the thus determined sub-partial products are mutually added to determine a result of multiplication (Ai.times.Bi). Since j is even, the number of partial multipliers (PAi)j is half the number of digits (or digit-1 for odd number) of the multiplier Ai.
Referring now to FIG. 3, a conventional product sum operation processing apparatus for execution of the above operation is illustrated in block diagram form. The conventional product sum operation processing apparatus has a partial product generating circuit 1 which receives a multiplier Ai from a multiplier input terminal T1 and a multiplicand Bi from a multiplicand input terminal T2 to generate partial products, a correction term generating circuit 2 which receives a sign bit SB of each of the partial products to generate a correction term of each sign, and an adder 3 which adds the partial products mutually to obtain a result of multiplication (Ai.times.Bi) and adds an augend/minuend C to the multiplication result (Ai.times.Bi) to deliver a product sum operation result Y.
The partial product generating circuit 1, based on Booth coding, is constructed as illustrated in block form in FIG. 4. As shown, the partial product generating circuit 1 has Booth decoders 11 which pick up even digits of the multiplier Ai to generate partial multipliers (PAi)j each having 3 bits corresponding to the even central digit, the preceding digit and the succeeding digit, generate sub-partial products of the partial multipliers (PAi)j and a multiplicand Bi and deliver sign bits SB of the individual sub-partial products. Thus, the Booth decoders 11 are identical in number to the partial multipliers (PAi)j.
Referring now to FIGS. 3 and 4, the operation of the conventional product sum operation apparatus will be described on the assumption that each of the multiplier Ai and the multiplicand Bi has 24 bits for convenience of explanation. Accordingly, the number of partial multipliers (PAi)j is 12 and the number of the Booth decoders 11 is 12. The partial product generating circuit 1 first receives the multiplier Ai inputted from the multiplier input terminal T1 and the multiplicand Bi inputted from the multiplicand input terminal T2, picks up even digits of the multiplier Ai to generate partial multipliers (PAi)j each having 3 bits corresponding to the even central digit, the preceding digit and the succeeding digit, and supplies the individual partial multipliers (PAi)j and the multiplicand Bi to the respective 12 Booth decoders 11 to cause them to operate in parallel, thus generating partial products based on the improved Booth decoding at a time.
Multiplication pursuant to the improved Booth decoding is indicated by the following equation: ##EQU1## where Sj represents sign bits of partial products and Pj represents sub-partial products.
In equation (2), the left term, that is, ##EQU2## indicates partial products delivered out of the partial product generating circuit, and the right term, that is, ##EQU3## indicates sign correction terms.
Equation (4) can be reduced to the following equation (5) by using the nature of 2' complement: ##EQU4##
Gathering from equation (5), it will be seen that the sign correction term in multiplication of N bits.times.N bits can be determined from a sign bit of the most significant bit of each sub-partial product. The correction term generating circuit 2 generates sign correction terms CB from sign bits SB of the individual sub-partial products. Three kinds of data pieces including the partial products delivered out of the partial product generating circuit 1, the sign correction terms CB generated by the correction term generating circuit 2 and the augend/minuend C supplied from the augend/minuend input terminal T4 are added together at a time to perform a product sum operation and a product sum operation result Y is delivered to an output terminal T5.
In the conventional product sum operation processing apparatus, however, when a circuit for executing the above calculation formulae as they are is constructed, the circuit scale of the partial product generating circuit increases as the number of bits to be calculated increases and because of an increase in the number of partial products, the circuit scale of the adder also increases, with the result that the overall circuit scale is increased.
Specifically, when each of the multiplier Ai and the multiplicand Bi has 24 bits and the above calculation formulae as they are are simply executed with a circuit, the circuit has a large scale of 31440 transistors.
Thus, the aforementioned conventional product sum operation apparatus has disadvantages that the circuit scale of the partial product generating circuit is increased as the number of bits to be calculated increases and because of an increased number of partial products, the circuit scale of the adder is increased, giving rise to an increase in the overall circuit scale.